package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         310,
		Discription: "形成高度最小的树的根节点组合",
		Level:       3,
		Labels: map[string]int{
			"拓扑排序": 1,
			"层序遍历": 1,
		},
	})
}

//一个推论：设节点x到节点y是树中最长的路径（之一），则形成高度最小的根节点必处在这条路径的中间（奇数一个，偶数两个）
//思路：
//1. 统计所有节点的度degrees []int、每个节点和哪些边连接nodeEdges [][]int
//2. 维持一个长度大于2的度为1的队列
//3. 首先将度为1的节点入队，然后删去这些节点，将与这些节点相连的节点的度-1，然后把度变为1的节点入队，继续下一轮
//4. 直到剩余节点的数量变为1或2，直接返回队列
func FindMinHeightTrees(n int, edges [][]int) []int {
	if n == 1 {
		return []int{0}
	}
	degrees := make([]int, n)
	nodeEdges := make([][]int, n)
	//注意是无向图，所以对于一条边中的两个节点的度都要+1，两个节点的连接的节点数组也都要统计
	for _, edge := range edges {
		x := edge[0]
		y := edge[1]
		degrees[x]++
		degrees[y]++
		nodeEdges[x] = append(nodeEdges[x], y)
		nodeEdges[y] = append(nodeEdges[y], x)
	}

	q := make([]int, 0)
	for nodeIndex, degree := range degrees {
		if degree == 1 {
			q = append(q, nodeIndex)
		}
	}

	leftNoddNum := n
	for leftNoddNum > 2 {
		levelLen := len(q)
		for i := 0; i < levelLen; i++ {
			nodeIndex := q[i]
			for _, nextNodeIndex := range nodeEdges[nodeIndex] {
				degrees[nextNodeIndex]--
				if degrees[nextNodeIndex] == 1 {
					q = append(q, nextNodeIndex)
				}
			}
		}
		q = q[levelLen:]
		leftNoddNum -= levelLen
	}

	return q
}
